#include <iostream>

using namespace std;
const int MOD=5000011;
const int N=1e5+10;


int s[N];
int f[N];
int main()
{
	int n,k;
	cin>>n>>k;
	f[0]=1;
	s[0]=1;
	for(int i=1;i<=n;i++)
	{
		f[i]=s[max(0,i-k-1)];
		s[i]=(s[i-1]+f[i])%MOD;
	}
	cout<<s[n]<<endl;

	return 0;
}
